package com.zjsru.oneDay202211;

/**
 * @Author: CookLee
 * @Date: 2022/11/20
 *
 * 香槟塔
 * 从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。
 * 当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）
 *
 * 示例 1:
 *  * 输入: poured(倾倒香槟总杯数) = 1, query_glass(杯子的位置数) = 1, query_row(行数) = 1
 *  * 输出: 0.00000
 *  * 解释: 我们在顶层（下标是（0，0））倒了一杯香槟后，没有溢出，因此所有在顶层以下的玻璃杯都是空的。
 *  *
 *  * 示例 2:
 *  * 输入: poured(倾倒香槟总杯数) = 2, query_glass(杯子的位置数) = 1, query_row(行数) = 1
 *  * 输出: 0.50000
 *  * 解释: 我们在顶层（下标是（0，0）倒了两杯香槟后，有一杯量的香槟将从顶层溢出，位于（1，0）的玻璃杯和（1，1）的玻璃杯平分了这一杯香槟，所以每个玻璃杯有一半的香槟。
 */
public class ChampagneTower {
    
    /**
     * 线性DP
     * 定义 tower[i][j] 为第 i 行第 j 列杯子所经过的水的流量（而不是最终剩余的水量）。
     */
    public double champagneTower(int poured, int query_row, int query_glass) {
        //防止溢出
        double[][] tower = new double[query_row + 10][query_row + 10];
        //第一个杯子获取全部的香槟 往下分
        tower[0][0] = poured;
        for (int i = 0; i < query_row; i++) {
            for (int j = 0; j < query_row; j++) {
                //不足时 即结束
                if (tower[i][j] <= 1) {
                    continue;
                }
                //香槟塔流到下一层时，中间的杯子会得到双份流量,即是每一个的杯子的下面的两个杯子均分剩余的酒
                tower[i + 1][j] += (tower[i][j] - 1) / 2;
                tower[i + 1][j + 1] = (tower[i][j] - 1) / 2;
            }
        }
        //多余一杯的时候 最大值即是1
        return Math.min(tower[query_row][query_glass], 1);
    }
    
    public static void main(String[] args) {
        ChampagneTower champagneTower = new ChampagneTower();
        int poured  = 2;
        int queryRow = 1;
        int queryGlass = 1;
        System.out.println(champagneTower.champagneTower(poured, queryRow, queryGlass));
    }
}
